Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Moving Average from Data Stream

Problem Statement

Given a stream of integers and window size n, calculate the moving average of all the integers of the sliding window.

Implement the Solution class:

  • MovingAverage(int size) Initializes the object with the size of the window size, which is n.
  • double next(int x) Calculates and returns the moving average of the last n values of the integer stream.

Examples

  • Example 1:

    • Input: ["MovingAverage", "next", "next", "next"], [[2], [1], [10], [3]]
    • Expected Output: [null, 1.0, 5.5, 6.5]
    • Justification: The moving average of the last 2 numbers. Initially, it's 1. Then (1+10)/2 = 5.5, and (10+3)/2 = 6.5.
  • Example 2:

    • Input: ["MovingAverage", "next", "next"], [[4], [5], [15]]
    • Expected Output: [null, 5.0, 10.0]
    • Justification: First, the average is 5. Then, (5+15)/2 = 10 as we consider the last 4 numbers, but only two numbers are in the stream.
  • Example 3:

    • Input: ["MovingAverage", "next", "next", "next", "next"], [[3], [7], [4], [8], [5]]
    • Expected Output: [null, 7.0, 5.5, 6.33, 5.67]
    • Justification: Moving average calculations are (7), (7+4)/2, (7+4+8)/3, and (4+8+5)/3.

Solution

To solve this problem, we can use a queue to store the most recent 'n' numbers. A queue is perfect for this task as it allows easy addition of new elements and removal of old elements, maintaining the 'window' of the last 'n' elements.

The approach is efficient as it avoids recalculating the sum from scratch for each new element. When a new number is added, we add it to the sum and enqueue it. If the queue exceeds the size 'n', we dequeue an element and subtract it from the sum. This way, we always have the sum of the last 'n' elements, allowing us to quickly calculate the new average.

Step-by-Step Algorithm

  • Initialize a queue and a variable to store the sum of the last 'n' elements.
  • When a new number arrives:
    • Add the number to the queue.
    • Add this number to the sum.
    • If the queue's size exceeds n:
      • Dequeue the oldest number from the queue.
      • Subtract this number from the sum.
    • Calculate the average by dividing the sum by the minimum of n or the queue's current size.

Algorithm Walkthrough

Let's use Example 3: ["MovingAverage", "next", "next", "next", "next"], [[3], [7], [4], [8], [5]]

  1. Initialization:

    • Create a queue to represent the moving window of size 3.
    • Initialize the sum to 0.
  2. First Value - next(7):

    • Enqueue '7': Add '7' to the queue. Queue now contains [7].
    • Update Sum: Sum = 0 + 7 = 7.
    • Calculate Average: Average = Sum / Queue Size = 7 / 1 = 7.0.
    • Queue State: [7], Sum: 7.
  3. Second Value - next(4):

    • Enqueue '4': Add '4' to the queue. Queue now contains [7, 4].
    • Update Sum: Sum = 7 + 4 = 11.
    • Calculate Average: Average = Sum / Queue Size = 11 / 2 = 5.5.
    • Queue State: [7, 4], Sum: 11.
  4. Third Value - next(8):

    • Enqueue '8': Add '8' to the queue. Queue now contains [7, 4, 8].
    • Update Sum: Sum = 11 + 8 = 19.
    • Calculate Average: Average = Sum / Queue Size = 19 / 3 ≈ 6.33.
    • Queue State: [7, 4, 8], Sum: 19.
  5. Fourth Value - next(5):

    • Queue Exceeds Size: Before adding '5', the queue size equals the window size (3).
    • Enqueue '5' and Dequeue '7':
      • Add '5' to the queue. Queue temporarily becomes [7, 4, 8, 5].
      • Remove '7' from the queue as it exceeds the window size. Queue now contains [4, 8, 5].
    • Update Sum: New Sum = Previous Sum - Dequeued Value + New Value = 19 - 7 + 5 = 17.
    • Calculate Average: Average = Sum / Queue Size = 17 / 3 ≈ 5.67.
    • Queue State: [4, 8, 5], Sum: 17.

Through each next operation, the queue dynamically updates to hold only the last 3 values, and the sum is adjusted to reflect the current window's total value, allowing the calculation of the moving average at each step.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity:

    • The time complexity is O(1) for each next operation, as adding, removing, and calculating the average are constant time operations.
  • Space Complexity:

    • The space complexity is O(n), where n is the size of the moving window, as we need to store up to n elements.
Moving Average from Data Stream (easy)
Move Zeroes (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis